/*
N个村庄修路，给你他们之间的花费(邻接矩阵)，然后还有一部分村庄已经修好路，求最小花费。
Sample Input
3
0 990 692
990 0 179
692 179 0
1
1 2
Sample Output
179
 */
package com.yuan.algorithms.training20150807;

import java.io.BufferedInputStream;
import java.util.Scanner;

/**
 * @author YouYuan
 * @eMail E-mail:1265161633@qq.com
 * @Time 创建时间：2015年8月24日 上午10:44:32
 * @Explain 说明:
 */
public class HDU1102_村庄修路 {

	static Scanner in = new Scanner(new BufferedInputStream(System.in));
	static final int S = 110, MAX = 0xfffffff;
	static int[][] map = new int[S][S];
	static boolean[] mark = new boolean[S];
	static int n;
	
	public static void main(String[] args) {
		while(in.hasNext()) {
			initialise();
			n = in.nextInt();
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					map[i][j] = map[j][i] = in.nextInt();
					if (i == j) {
						map[i][j] = map[j][i] = MAX;
					}
				}
			}
			int q = in.nextInt();
			while(--q>=0) {
				int a = in.nextInt();
				int b = in.nextInt();
				map[a][b] = map[b][a] = 0;
			}
			prim();
		}
	}

	private static void prim() {
		mark[1] = true;
		int sum = 0;
		for (int i = 1; i < n; i++) {
			int min = MAX;
			int index = -1;
			for (int j = 1; j <= n; j++) {
				if (!mark[j] && map[1][j] < min) {
					min = map[1][j];
					index = j;
				}
			}
			if (index == -1) {
				return;
			}
			sum += min;
			mark[index] = true;
			for (int j = 1; j <= n; j++) {
				if (!mark[j] && map[index][j] < map[1][j]) {
					map[1][j] = map[index][j];
				}
			}
		}
		System.out.println(sum);
	}

	private static void initialise() {
		for (int i = 1; i <= n; i++) {
			mark[i] = false;
			for (int j = 1; j <= n; j++) {
				map[i][j] = MAX;
			}
		}
	}

}
